This invention relates generally to graphic rendering, and more particularly to representing graphic objects using hierarchical data structures and surface elements.
Three-dimensional computer graphics have become ubiquitous at the consumer level. There is a proliferation of affordable 3D graphics hardware accelerators, from high-end PC workstations to low-priced game stations. However, interactive computer graphics have still not reached the level of realism that allows a true immersion into a virtual world. For example, typical foreground characters in real-time games are extremely minimalistic polygon models that often exhibit annoying artifacts, such as angular silhouettes.
Various sophisticated modeling techniques, such as implicit surfaces, or subdivision surfaces, allow the creation of 3D graphics models with increasingly complex shapes. Higher order modeling primitives, however, are eventually decomposed into triangles before being rendered by the graphics subsystem. The triangle as a rendering primitive seems to meet the right balance between descriptive power and computational burden. To render realistic, organic-looking models requires highly complex shapes with ever more triangles, or, as stated by Smith in xe2x80x9cSmooth Operator,xe2x80x9d The Economist, pp. 73-74, Mar. 6, 1999, xe2x80x9creality is 80 million polygons.xe2x80x9d
Processing many small triangles leads to bandwidth bottlenecks and excessive floating point number calculations and rasterization requirements. To increase the apparent visual complexity of objects, texture mapping has been introduced. Textures convey more detail inside a polygon, thereby allowing larger and fewer triangles to be used. Today""s graphics engines are highly tailored for high texture mapping performance. However, texture maps have to follow the underlying geometry of the polygon model and work best on flat or slightly curved surfaces. Realistic or xe2x80x9corganicxe2x80x9d surfaces frequently require a large number of textures that have to be applied in multiple passes during rasterization.
Advanced rendering techniques, such as Phong shading, bump mapping, and displacement mapping, are not handled by most current consumer graphics systems. Graphic phenomena such as smoke, fire, or water are difficult to render using textured triangles.
In computer graphics, one can represent objects in 3D space in many different ways using various primitive graphic elements. The known representations that are commonly used to represent graphic objects are implicit, geometric, volumetric, and point sample.
In an implicit representation, the graphic object can be generated from arbitrary mathematical and/or physical functions. For example, to draw the outline of a hollow sphere one simply supplies the rendering engine with the function (in Cartesian coordinates) x2+y2+z2=r, and for a solid sphere the function is x2+y2+z2xe2x89xa6r. Color and other material properties can similarly be synthetically generated. Functions can be used to describe various geometric shapes, physical objects, and real or imaginary models. Implicit functions are not suitable for synthezising complex objects, for example, a human figure.
Classically, 3D objects have been geometrically modeled as a mesh of polygonal facets. Usually, the polygons are triangles. The size of each facet is made to correspond mostly to the degree of curvature of the object in the region of the facet. Many polygons are needed where the object has a high degree of curvature, fewer for relatively flat regions. Polygon models are used in many applications, such as, virtual training environments, 3D modeling tools, and video games. As a characteristic, geometric representations only deal with the surface features of graphic objects.
However, problems arise when a polygon model is deformed because the size of the facets may no longer correspond to local degrees of curvature in the deformed object, after all, a triangle is flat. Additionally, deformation may change the relative resolution of local regions. In either case, it becomes necessary to re-mesh the object according to the deformed curvature. Because re-meshing (polygonization) is relatively expensive in terms of computational time, it is usually done as a preprocessing step. Consequently, polygon models are not well suited for objects that need to be deformed dynamically.
In an alternative representation, the object is sampled in 3D space to generate a volumetric data set, for example, a MRI or CT scan. Each sample is called a voxel. A typical data set may include millions of voxels. To render a volumetric data set, the object is typically segmented. Iso-surfaces can be identified to focus on specific volumetric regions. For instance, a volumetric data set of the human head may segment the voxels according to material properties, such as bone and soft tissue.
Because of the large number of voxels, physically-based modeling and the deformation of volumetric data sets is still a very computationally expensive operation. Often, one is only interested in surface features, and the interior of the object can effectively be ignored.
A point sample representation of objects is often used to model fluid flows, for example, in wind tunnel simulations. Certain attributes, such as orientation velocity, are given to point samples in order to track individual point samples through the fluid flow, or to visualize the complete flow.
Another application of point sample representation is in the visualization of xe2x80x9ccloud-likexe2x80x9d objects, such as smoke, dust or mist. A shading model can be applied to point samples that emit light to render cloud-like objects. Also, point samples can be constrained to subspaces with the help of energy functions to model surfaces. An advantage of point sample clouds is that the clouds are very deformable. As a disadvantage, the point samples in the cloud are unconnected and behave individually when exposed to forces. Furthermore, prior art point samples are quite unsuitable for representing surfaces of solid objects or models.
The rendering time for these conventional primitives depends on the complexity of the objects modeled. For example, with a geometric representation of a complex object, the polygons are typically very small in size, in the order of a very small number of pixels, and the object is represented by many polygons. The polygons are usually represented with vertices that define a triangle.
To render a polygon, the projection of the triangle is scan-converted (rasterized) to calculate the intensity of each pixel that falls within the projection. This is a relatively time consuming operation when only a few pixels are covered by each polygon. Replacing the polygons with point samples and projecting the point samples to the image can be a more efficient technique to render objects.
A number of techniques are known for rendering volumes. In general, volume rendering is quite complex. Unless the number of voxels is limited, real-time rendering can be time consuming, or impractical for real-time applications.
A real-time rendering system, described in U.S. Pat. No. 5,781,194 xe2x80x9cReal-time Projection of Voxel-based Objects,xe2x80x9d issued to Ponomarov et al. on Jul. 14, 1998, constructs a chain of surface voxels using incremental vectors between surface voxels. That representation succeeds in modeling and displaying objects showing highly detailed surface regions. The modeling of rigid body motion is done with the aid of scripting mechanisms that lack realism because physically-based methods are not used.
The use of points as rendering primitives has a long history in computer graphics. Catmull, in xe2x80x9cA Subdivision Algorithm for Computer Display of Curved Surfaces,xe2x80x9d Ph.D. thesis, University of Utah, December 1974, observed that geometric subdivision may ultimately lead to points on surfaces. Particles were subsequently used for objects, such as clouds, explosions, and fire, that could not be rendered with other methods, see Reeves in xe2x80x9cParticle Systemsxe2x80x94A Technique for Modeling a Class of Fuzzy Objects, SIGGRAPH Proceedings, pp. 359-376. July 1983.
Visually complex objects have been represented by dynamically generated image sprites. Sprites are fast to draw and largely retain the visual characteristics of the object, see Shade et al. in xe2x80x9cLayered Depth Images,xe2x80x9d SIGGRAPH Proceedings, pp. 231-242. July 1998. A similar approach was used in the Talisman rendering system to maintain high and approximately constant frame rates, see Torborg et al. in xe2x80x9cTalisman: Commodity Real-Time 3D Graphics for the PC,xe2x80x9d SIGGRAPH Proceedings, pp. 353-364, August 1996. However, mapping objects onto planar polygons leads to visibility errors and does not allow for parallax and disocclusion effects. To address these problems, several methods add per-pixel depth information to images, variously called layered impostors, sprites with depth, or layered depth images, just to name a few. Still, none of these techniques provides a complete object model that can be illuminated and rendered from arbitrary points of view.
All these methods use view-dependent, image centered samples to represent an object or scene. However, view-dependent samples are ineffective for dynamic scenes with motion of objects, changes in material properties, and changes in position and intensities of light sources.
Levoy et al. in xe2x80x9cThe Use of Points as a Display Primitive,xe2x80x9d University of North Carolina Technical Report 85-022, 1985, describe a process for converting an object to a point representation. There, each point has a position and a color. They also describe a process to render the points as a smooth surface. The points are modeled as zero-dimensional samples, and are rendered using an object-order projection. When rendering, multiple points can project to the same pixel and the intensities of these points may need to be filtered to obtain a final intensity for the pixel under consideration. This filtering is done by weighting the intensity proportional to the distance from the projected point position in the image to the corresponding pixel-center, whereas the weights are normalized according to the partial coverage of a pixel by a surface. The coverage is estimated by calculating the density of the projected points in image space and the weighting is modeled with a Gaussian filter. An enhanced depth-buffer (z-buffer) allows for depth comparisons with a tolerance that enables the blending of points in a small region of depth-values. Their point representation allows one to render the object from any point of view.
In another technique, as described by Grossman et al. in xe2x80x9cPoint Sample Rendering,xe2x80x9d Proceedings of the Eurographics Workshop ""98, Rendering Techniques 1998, pp. 181-192, July 1998, the point samples are obtained by sampling orthographic projections of an object on an equilateral triangle lattice. The equilateral triangle lattice was preferred to a quadrilateral one because the spacing between adjacent sampling points is more regular.
Dally et al., in xe2x80x9cThe Delta Tree: An Object-Centered Approach to Image-Based Rendering,xe2x80x9d Technical Report AIM-1604; MIT, May 1996, introduced the delta tree as an object-centered approach to image-based rendering. The movement of the viewpoint in their method, however, is still confined to particular locations.
Chang et al., in xe2x80x9cLDI Tree: A Hierarchical Representation for Image-Based Rendering,xe2x80x9d SIGGRAPH Proceedings, pp. 291-298, August 1999, presented the LDI tree, a hierarchical space partitioning data structure for image based rendering.
All of the known representations have some limitations. Therefore, what is needed is an object representation that combines the best features of each and simplifies rendering.
The present invention provides a method for rendering objects with rich shapes and textures at interactive frame rates. The method is based on surface elements (surfels) as rendering primitives. Surfels are point samples of a graphics model. In a preprocessing stage, the surfaces of complex geometric models are sampled along three orthographic views. The invention adaptively samples the object using image space resolution. At the same time, computation-intensive calculations such as texture, bump, or displacement mapping are performed. By moving rasterization and texturing from the core rendering pipeline to the preprocessing step, the rendering cost is dramatically reduced.
From a rendering point of view, the surfel representation according to the invention provides a discretization of the geometry, and hence, reduces the object representation to the essentials needed for rendering. By contrast, triangle primitives implicitly store connectivity information, such as vertex valence or adjacencyxe2x80x94data not necessarily available or needed for rendering.
Storing normals, prefiltered textures, and other per surfel data enables one to build high quality rendering processes. Shading and transformations is applied on a per surfel basis to achieve Phong illumination, bump and displacement mapping, as well as other advanced rendering features.
The rendering also provides environment mapping with a painterly surfel rendering process running at interactive frame rates. A hierarchical forward projection algorithm allows one to estimate the surfel density per output pixel for speed-quality tradeoffs.
A surfel rendering pipeline complements existing graphics pipelines. The pipeline trades memory overhead for rendering performance and quality. The present invention is suitable for interactive 3D applications, particularly for organic objects with high surface details, and for applications where preprocessing is not an issue. These qualities make the present invention ideal for interactive games.
Surfels according to the invention are a powerful paradigm to efficiently render complex geometric objects at interactive frame rates. Unlike classical surface discretizations, i.e., triangles or quadrilateral meshes, surfels are point primitives without explicit connectivity. Surfel attributes comprise depth, texture color, normal, and others. As a preprocess, an octree-based surfel representation of a geometric object is constructed. During sampling, surfel positions and normals are optionally perturbed, and different levels of texture colors are prefiltered and stored per surfel in a view independent manner.
During rendering, a hierarchical forward warping algorithm projects surfers to a z-buffer (depth buffer). A novel method called visibility splatting determines visible surfels and holes in the z-buffer. Visible surfels are shaded using texture filtering, Phong illumination, and environment mapping using per-surfel normals. Several methods of image reconstruction, including supersampling, offer flexible speed-quality tradeoffs. Due to the simplicity of the operations, the surfel rendering pipeline is amenable for a hardware implementation. Surfel objects offer complex shape, low rendering cost and high image quality, which makes them specifically suited for low-cost, real-time graphics, such as games.
More particularly, a rendering system includes a memory storing shape and shade attributes of a surface of the object. The attributes are arranged as an octree in the memory. The octree includes a plurality of nodes arranged at a plurality of levels, each node storing a plurality of zero-dimensional n-tuples, each n-tuple locally approximating the shape and shade attributes of a portion of the surface of the graphic object, and the n-tuples having a sampling resolution of an image space. A plurality of parallel processing pipelines are connected the memory. The pipelines project the shape and shade attributes of the octree to an image plane having a selected orientation by traversing the n-tuples of the nodes of the octree from a lowest resolution level to a highest resolution level.
The graphic object is sampled by casting rays through the object. The rays originate at orthogonal planes surrounding the object. The surface of the object is sampled for shape and shade attributes at points where the rays intersect the surface. The sampled shape and shade attributes of each sampled point are stored in the octree stored in the memory.
Shade attributes of the surface points of the a graphic object are filtered by constructing tangential disks at positions of each surface point. The tangential disks have increasingly larger radii. Each tangential disk is projected to an ellipse in texture space. View independent filter functions are applied at the position of each surface point to generate texture mipmaps for the surface point. The filter functions have an extent equal to the projected tangential disk. The surface point is projected to the pixels in the depth buffer, and a view dependent filter function is applied to each pixel in the image buffer to determine colors for the pixels.